import entity.TreeNode;

public class ValidateBinarySearchTree {
    /*
    * 98. 验证二叉搜索树
    * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
    * 有效 二叉搜索树定义如下：
    * 节点的左子树只包含 小于 当前节点的数。
    * 节点的右子树只包含 大于 当前节点的数。
    * 所有左子树和右子树自身必须也是二叉搜索树。
    *
    * 树中节点数目范围在[1, 10^4] 内
    * -2^31 <= Node.val <= 2^31 - 1
    * */
    public static void main(String[] args){

    }

    // 我的想法：所有左子树和右子树自身必须也是二叉搜索树,可以递归，
    // 由于发现不合适的就要返回，因此递归函数要返回值
    // 错误！！！看清楚定义：节点的==左子树==只包含 小于 当前节点的数。节点的==右子树==只包含 大于 当前节点的数。
    // 也就是说，子数上的所有值都得大于或小于中间节点
    public boolean mySolution(TreeNode root){
        if(root==null)
            return true;
        if(root.left != null && root.val <= root.left.val)
            return false;
        if(root.right != null && root.val >= root.right.val)
            return false;
        return mySolution(root.right) && mySolution(root.left);
    }

    TreeNode max;
    // 二叉排序树的中序遍历是递增的！这个性质很重要
    // 你甚至可以按照中序遍历顺序把树转化为数组，判断数组是否是单调递增的就行了
    // 得用中序遍历，先序遍历无法在递归过程中控制比根大还是小
    // 确实，得从地下开始向上判断，而不是从顶向下判断
    public boolean isValidBST(TreeNode root) {
        if(root==null)
            return true;
        if(!isValidBST(root.left))
            return false;
        if(max != null && root.val <= max.val)
            return false;
        max = root;
        return isValidBST(root.right);
    }
}
